home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1996 January / macformat-033.iso / mac / Shareware City / Developers / VideoToolbox / VideoToolboxSources / randU.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-04-09  |  4.8 KB  |  136 lines  |  [TEXT/CWIE]
  1. /*
  2. randU.c
  3. Denis G. Pelli
  4.  
  5. i=randU();
  6. randU() is the Standard C random number generator rand()--see K&R--modified to
  7. return 16 bits as an unsigned short int instead of just 15 bits as a (positive)
  8. short int. Both versions satisfy Knuth's prescriptions for a linear congruential
  9. random number generator, namely, given that the modulus is 2^32, the multiplier
  10. should be between 0.01m and 0.99m, the multiplier mod 8 should be 5, and the
  11. addend should be odd. (Knuth also recommends doing spectral testing of the
  12. multiplier, and I don't know if that's been done. One would like to think that
  13. the Standard C committee would have chosen a multiplier that had been so tested.)
  14.  
  15. j=randUL();
  16. randUL() returns a 32-bit random number, formed by calling randU() twice and
  17. gluing the results together.
  18.  
  19. RandFill(address,bytes);
  20. RandFill is a tight coding of randU() optimized for filling large buffers. It's twice
  21. as fast as making repeated calls to randU(), but is numerically equivalent, and even 
  22. uses the same seed. For high speed it must be compiled to use the 68020 (or better)
  23. chip, otherwise each long multiplication requires a subroutine call. 
  24. Fills 0.8 MB/s on a Mac IIci, i.e. 25 MHz 68030.
  25.  
  26. Kernighan, B. W. and Ritchie, D. M. (1988) The C Programming Language, Second
  27. Ed. Englewood Cliffs, NJ: Prentice Hall, p. 46.
  28.  
  29. Knuth, D. E. (1981) The Art of Computer Programming: 2. Seminumerical
  30. Algorithms, Second Edition.  Reading, MA: Addison Wesley. pp. 170-171.
  31.  
  32. HISTORY:
  33. 8/4/89    dgp    wrote it.
  34. 3/19/90    dgp    eliminated assembly code to make it portable. 
  35. 8/5/91    dgp    added RandFill(). 
  36. 8/24/91    dgp    Made compatible with THINK C 5.0.
  37. 10/21/91 dgp Removed obsolete inclusion of MacProto.h.
  38. 9/13/92    dgp    Added randUL().
  39. */
  40. #include "VideoToolbox.h"
  41.  
  42. typedef union {
  43.     unsigned long L;
  44.     struct {
  45.         short high;
  46.         short low;
  47.     } S;
  48. } seedType;
  49.  
  50. static seedType seed={314159265};
  51.  
  52. unsigned short randU(void)
  53. {
  54.     seed.L = seed.L * 1103515245L + 12345L;
  55.     return seed.S.high;
  56. }
  57.  
  58. #if USHRT_MAX!=0xffff || ULONG_MAX!=0xffffffff
  59.     #error "randUL() assumes 16 bit unsigned short and 32 bit unsigned long"
  60. #endif
  61.  
  62. unsigned long randUL(void)
  63. {
  64.     return ((unsigned long)randU()<<16)+randU();
  65. }
  66.  
  67. /*    srandU - seed pseudo-random number generator    */
  68.  
  69. void srandU(unsigned n)
  70. {
  71.     seed.L = n;
  72. }
  73.  
  74. /*
  75. RandFill uses exactly the same algorithm as randU, using the same seed, but is
  76. coded to fill a large buffer quickly.
  77.  
  78. The trick here is to avoid having to do a bit shift to get at the high word of
  79. the s register. I do this by moving the entire long register to memory,
  80. overwriting the least significant two bytes on the next iteration. As a result
  81. this method requires a 2 byte overhang beyond the end of the desired data. That
  82. overhang region and an odd byte, if any, is filled in by copying from a
  83. workArea.
  84.  
  85. A simpler way to implement this overhang business would have been to copy the
  86. memory that was to be overwritten, overfill the buffer, and then restore the
  87. overwritten memory. The problem with that method is that it assumes the
  88. overwritten memory exists (e.g. it might be video memory) and won't be used
  89. while we're running, which is not an entirely safe assumption unless we turn off
  90. interrupts. So I took the cautious approach, which makes for a messier looking
  91. program, but it's safe. The performance cost is negligible.
  92. */
  93. void RandFill(void *address,long bytes)
  94. {
  95.     register long i;
  96.     register unsigned long s,mul,add;
  97.     register unsigned short *ptr;
  98.     unsigned short *savePtr,workArea[3];
  99.  
  100.     s=seed.L;
  101.     mul=1103515245L;
  102.     add=12345L;
  103.     ptr=(unsigned short *)address;
  104.     i=bytes;
  105.     i-=2;                    /* allow guard room for overshoot */
  106.     /* Because of the unrolling, the loop overhead is only 3% of running time */
  107.     for(;i>=32;i-=32) {
  108.         /* this compiles to 4 instructions: MULU.L, ADD.L, MOVE.L, ADDQ.L */
  109.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  110.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  111.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  112.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  113.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  114.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  115.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  116.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  117.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  118.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  119.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  120.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  121.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  122.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  123.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  124.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  125.     }
  126.     for(;i>=2;i-=2) {
  127.         s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  128.     }
  129.     i+=2;                    /* remove guard */
  130.     savePtr=ptr;
  131.     ptr=&workArea[0];
  132.     s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  133.     s *= mul; s += add; *(unsigned long *)ptr=s; ptr++;
  134.     memcpy(savePtr,workArea,i);
  135.     seed.L=s;
  136. }